This randomized, double-blind study will compare MK-639 alone and in combination with zidovudine to zidovudine with respect to changes in surrogate markers of disease activity. Zidovudine is approved for adult patients with CD4 counts < 500 cells/mm3 and is considered recommended therapy for the patient population included in this study. Efficacy will be evaluated by comparing CD4 counts in patients receiving MK-639 800 mg q8h alone or in combination with zidovudine 200 mg q8h to CD4 counts in patients receiving zidovudine 200 mg q8h alone. Although it is not the primary objective of this study and the study is not powered to detect a difference among treatments in clinical endpoints, efficacy may be evaluated by comparing the incidence of opportunistic infections or death to see if there is a trend in differences. Safety will be carefully evaluated using clinical and laboratory parameters.